#include <cstdio>
using namespace std;
/*
 * @lc app=leetcode.cn id=234 lang=cpp
 *
 * [234] 回文链表
 */

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    // 真的烦, 反转之后还要重新反转过来
    
    bool isPalindrome(ListNode* head) {
        // 1 2 3 2 1
        if (!head || !head->next) return true;
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            fast = fast->next->next;
            if (fast) slow = slow->next;
        }
        ListNode *tail = reverseList(slow);
        ListNode *temp = tail;
        do {
            if (tail->val != head->val) return false;
            tail = tail->next; head = head->next;
        } while (head != nullptr);

        reverseList(tail);
        return true;

    }

    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* pre = nullptr, *current = head, *last = nullptr;
        while (current) {
            last = current->next;
            current->next = pre;
            pre = current;
            current = last;
        }
        return pre;
    }
};
// @lc code=end

